{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Deletions to Make Array Beautiful"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDeletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #美化数组的最少删除数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，如果满足下述条件，则认为数组 <code>nums</code> 是一个 <strong>美丽数组</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length</code> 为偶数</li>\n",
    "\t<li>对所有满足 <code>i % 2 == 0</code> 的下标 <code>i</code> ，<code>nums[i] != nums[i + 1]</code> 均成立</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，空数组同样认为是美丽数组。</p>\n",
    "\n",
    "<p>你可以从 <code>nums</code> 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 <strong>不变</strong> 。</p>\n",
    "\n",
    "<p>返回使 <code>nums</code> 变为美丽数组所需删除的 <strong>最少</strong> 元素数目<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,2,3,5]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>可以删除 <code>nums[0]</code> 或 <code>nums[1]</code> ，这样得到的 <code>nums</code> = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,2,2,3,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以删除 <code>nums[0]</code> 和 <code>nums[5]</code> ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-deletions-to-make-array-beautiful](https://leetcode.cn/problems/minimum-deletions-to-make-array-beautiful/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-deletions-to-make-array-beautiful](https://leetcode.cn/problems/minimum-deletions-to-make-array-beautiful/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,3,5]', '[1,1,2,2,3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        flag = True\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            if flag:\n",
    "                if nums[i] == nums[i + 1]:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    flag = False\n",
    "            else:\n",
    "                flag = True\n",
    "        nums.clear()\n",
    "        if flag:\n",
    "            return ans + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if nums[i]==-1:\n",
    "                i=i+1\n",
    "                continue\n",
    "            j=i\n",
    "            while (j<n)and(nums[j]==nums[i]):\n",
    "                j+=1\n",
    "            j-=1\n",
    "            l=j-i+1\n",
    "            ans+=l-1\n",
    "            if j+1<n:\n",
    "                nums[j+1]=-1\n",
    "            i=j+1\n",
    "        if (n-ans)%2==1:\n",
    "            ans+=1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        while len(nums) > 1:\n",
    "            if nums[-1] != nums[-2]:\n",
    "                nums.pop()\n",
    "                nums.pop()\n",
    "            else:\n",
    "                nums.pop()\n",
    "                res += 1\n",
    "        res += len(nums) == 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = 0\n",
    "        while len(nums) >= 2:\n",
    "            if nums[-1] != nums[-2]:\n",
    "                nums.pop(), nums.pop()\n",
    "            else:\n",
    "                nums.pop()\n",
    "                a += 1\n",
    "        return a + len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.reverse()\n",
    "        ans = 0\n",
    "        cur = -1\n",
    "        while nums:\n",
    "            if cur == -1:\n",
    "                cur = nums.pop()\n",
    "            else:\n",
    "                if nums.pop() != cur:\n",
    "                    ans += 2\n",
    "                    cur = -1\n",
    "        return n - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        \"Beautiful\" array:\n",
    "            - len(nums) is even\n",
    "            - nums[i] != nums[i + 1] when i is even\n",
    "\n",
    "        Deletion on nums[i]: \n",
    "        delete it and shift all elements on its right by one unit\n",
    "\n",
    "        ==> Start from the end of array, delete invalid elements\n",
    "\n",
    "            Finally, if len(nums) is odd, delete the last one\n",
    "            (so that we don't need to shift elements)\n",
    "        \"\"\"\n",
    "\n",
    "        def duplicate_on_odd(num: int) -> bool:\n",
    "            if len(beautiful_array) % 2 == 0:\n",
    "                return False\n",
    "            # Odd length and not empty\n",
    "            return beautiful_array[-1] == num\n",
    "\n",
    "        n = len(nums)\n",
    "        beautiful_array = []\n",
    "        while nums:\n",
    "            num = nums.pop()\n",
    "            if duplicate_on_odd(num):\n",
    "                continue\n",
    "            beautiful_array.append(num)\n",
    "\n",
    "        n_deletion = n - len(beautiful_array)\n",
    "\n",
    "        # Odd length\n",
    "        if len(beautiful_array) % 2 != 0:\n",
    "            n_deletion += 1\n",
    "\n",
    "        return n_deletion\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 1\n",
    "        ans,i = 0,0\n",
    "        while i < len(nums) - 1:\n",
    "            if nums[i] == nums[i+1]:\n",
    "                ans += 1\n",
    "                i -= 1\n",
    "            i += 2\n",
    "        if (len(nums) - ans) & 1:ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "tips.0 : 用range(1, length) 和 i == i-1来避免越界\n",
    "tips.1 : 记录在i位之前删除的字符数量n，用i-n判断i是不是需要和i-1判断并删除i-1\n",
    "tips.2 ：必须为偶数，所以len-n为奇数时最后删除多余的一位\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        delete = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if (i-delete)%2:\n",
    "                if nums[i] == nums[i-1]:\n",
    "                    delete += 1\n",
    "        return delete + (len(nums)-delete)%2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        stack,delta = [nums[0]],0\n",
    "        for i in range(1,len(nums)):\n",
    "            if len(stack)%2:\n",
    "                if nums[i]!=stack[-1]:\n",
    "                    stack.append(nums[i])\n",
    "                else:\n",
    "                    delta+=1\n",
    "            else:\n",
    "                stack.append(nums[i])\n",
    "        return delta+len(stack)%2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        last = -1\n",
    "        t = 0\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            if(t == 0):\n",
    "                last = n\n",
    "                t = 1-t\n",
    "            else:\n",
    "                if(n == last):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    last =  n\n",
    "                    t = 1- t\n",
    "        if(t):\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans, cnt = 0, 0\n",
    "        two = set()\n",
    "        for num in nums:\n",
    "            two.add(num)\n",
    "            cnt += 1\n",
    "            if len(two) == 2:\n",
    "                ans += cnt - 2\n",
    "                cnt = 0\n",
    "                two.clear()\n",
    "        return ans + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        stack,delte = [nums[0]],0\n",
    "        for i in range(1,len(nums)):\n",
    "            if len(stack)%2:\n",
    "                if nums[i]!=stack[-1]:\n",
    "                    stack.append(nums[i])\n",
    "                else:\n",
    "                    delte+=1\n",
    "            else:\n",
    "                stack.append(nums[i])\n",
    "        return delte+len(stack)%2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans, count = 0, 0\n",
    "        i, s = 0, []\n",
    "        while(i < len(nums)):\n",
    "            if len(s)%2 == 0:\n",
    "                s.append(nums[i])\n",
    "            elif nums[i] != s[-1]:\n",
    "                s.append(nums[i])\n",
    "            elif nums[i] == s[-1]:\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        if len(s)%2:\n",
    "            return ans + 1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res, last = 0, -1\n",
    "        for i in range(n):\n",
    "            if res % 2 == 0 or nums[i] != last:\n",
    "                res += 1\n",
    "                last = nums[i]\n",
    "        return n - res + (res % 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "\n",
    "        st = []\n",
    "        for i in nums:\n",
    "            if len(st) % 2 == 0: st.append(i)\n",
    "            else:\n",
    "                if st[-1] != i: st.append(i)\n",
    "\n",
    "        m, n = len(nums), len(st)\n",
    "        return m - n if n % 2 == 0 else m - n + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        last = -1\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if last == -1:\n",
    "                last = num\n",
    "            elif last != num:\n",
    "                last = -1\n",
    "                res += 2\n",
    "        return n - res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1] and (i-res) & 1 == 1:\n",
    "                res += 1\n",
    "\n",
    "        if (len(nums) - res) & 1 == 1:\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == nums[i-1] and (i-res) & 1 == 1:\n",
    "                res += 1\n",
    "\n",
    "        if (len(nums) - res) & 1 == 1:\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res=0\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        while i<n-1:\n",
    "            if nums[i]==nums[i+1]:\n",
    "                res+=1\n",
    "            else:\n",
    "                i+=1\n",
    "            i+=1\n",
    "        if (n-res)%2:\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        st = deque()\n",
    "        for n in nums:\n",
    "            if len(st) & 1 == 1 and n == st[-1]:\n",
    "                st.pop()\n",
    "            st.append(n)\n",
    "        if len(st) & 1 == 1: st.pop()\n",
    "        return len(nums) - len(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ln = len(nums)\n",
    "        stk = []\n",
    "        flag = 0\n",
    "        ans = 0\n",
    "        for i in range(ln):\n",
    "            if len(stk) == 0:\n",
    "                stk.append(nums[i])\n",
    "                flag = 1\n",
    "            else:\n",
    "                if flag == 1:\n",
    "                    if nums[i] == stk[-1]:\n",
    "                        ans += 1\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        stk.append(nums[i])\n",
    "                        flag = 0\n",
    "                else:\n",
    "                    stk.append(nums[i])\n",
    "                    flag = 1\n",
    "        return ans+1 if (ln-ans)%2==1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ret, i = 0, 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ret += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        if (n - ret) % 2 != 0:\n",
    "            ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans, stack = 0, []\n",
    "        for num in nums:\n",
    "            if len(stack) & 1:\n",
    "                if num == stack[-1]:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    stack.append(num)\n",
    "            else:\n",
    "                stack.append(num)\n",
    "\n",
    "        return ans + 1 if len(stack) & 1 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        stack=list()\n",
    "        for i in nums:\n",
    "            if (len(stack)%2==1) and (stack and stack[-1] == i): continue \n",
    "            stack.append(i)\n",
    "        if len(stack)%2==1:stack.pop()\n",
    "        return len(nums)-len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: list[int]) -> int:\n",
    "        idx, ans = 0, 0\n",
    "        for x in nums:\n",
    "            if idx == 0:\n",
    "                pre = x\n",
    "                idx = 1 - idx\n",
    "            elif x != pre:\n",
    "                idx = 1 - idx\n",
    "                ans += 2\n",
    "        return len(nums)-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        i = -1\n",
    "        for x in nums:\n",
    "\n",
    "            if st and ( i % 2 == 0) and st[-1] == x:\n",
    "                ans += 1\n",
    "                continue\n",
    "            st.append(x)\n",
    "            i += 1\n",
    "        \n",
    "        return ans + (len(st) % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        dp[-2] = 1\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] + 1 if nums[i] == nums[i + 1] else dp[i + 2]\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        s = []\n",
    "        for x in nums:\n",
    "            s.append(x)\n",
    "            if len(s) and len(s) % 2 == 0 and s[-2] == s[-1]:\n",
    "                s.pop()\n",
    "        if len(s) % 2:\n",
    "            s.pop()\n",
    "        return len(nums) - len(s)\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[-2] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                dp[i] = dp[i + 1] + 1\n",
    "            else:\n",
    "                dp[i] = dp[i + 2]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        dp[-2] = 1\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] + 1 if nums[i] == nums[i + 1] else dp[i + 2]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        last = None\n",
    "        for n in nums:\n",
    "            if cnt % 2 == 0 or last != n:\n",
    "                cnt += 1\n",
    "                last = n\n",
    "        if cnt % 2: cnt -= 1\n",
    "        return len(nums) - cnt\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        result = [0] * (len(nums) + 1)\n",
    "        result[-1] = 0\n",
    "        result[-2] = 1\n",
    "        for i in range(len(nums) - 2, -1 , -1):\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                result[i] = result[i + 1] + 1\n",
    "            else:\n",
    "                result[i] = result[i + 2]\n",
    "        return result[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        dp[-2] = 1\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            dp[i] = dp[i + 1] + 1 if nums[i] == nums[i + 1] else dp[i + 2]\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDeletion(self, nums: List[int]) -> int:\r\n",
    "        lis = []\r\n",
    "        start = 0\r\n",
    "        for i in range(len(nums) - 1):\r\n",
    "            if nums[i] != nums[i + 1]:\r\n",
    "                lis.append(i - start + 1)\r\n",
    "                start = i + 1\r\n",
    "        lis.append(len(nums) - start)\r\n",
    "        ans = 0\r\n",
    "        flag = False\r\n",
    "        for val in lis:\r\n",
    "            if val == 1:\r\n",
    "                flag = not flag\r\n",
    "            else:\r\n",
    "                if flag:\r\n",
    "                    ans += val - 2\r\n",
    "                else:\r\n",
    "                    ans += val - 1\r\n",
    "                    flag = not flag\r\n",
    "        if flag:\r\n",
    "            return(ans + 1)\r\n",
    "        return(ans)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        stk = [nums[0]]\n",
    "        idx = 0  # 记录栈顶元素的下标,用来判断当前下标的奇偶\n",
    "        for i in range(1,n):\n",
    "            if idx%2==0 and nums[i] == stk[-1]:\n",
    "                continue\n",
    "            stk.append(nums[i])\n",
    "            idx += 1\n",
    "\n",
    "        m = len(stk)\n",
    "        if m % 2 != 0:\n",
    "            m -= 1\n",
    "        return n-m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        if (n - ans) & 1:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        if l <= 1:\n",
    "            return l\n",
    "        while i + 1 < l:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1 \n",
    "            i += 1\n",
    "        if (l - ans) % 2:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        if l == 1:\n",
    "            return 1\n",
    "        elif l == 0:\n",
    "            return 0\n",
    "        while i + 1 < l:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                i += 1 \n",
    "            i += 1\n",
    "        if (l - ans) % 2:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i+1 < n:\n",
    "            if (i-res)%2 == 1:\n",
    "                i += 1\n",
    "                continue\n",
    "            # print(i, nums[i])\n",
    "            d = 0 # 后面有几个相同的\n",
    "            while i+d+1 < n and nums[i] == nums[i+d+1]:\n",
    "                d += 1\n",
    "            res += d\n",
    "            i += d+1\n",
    "            # print(res)\n",
    "        if (len(nums)-res) %2==1:\n",
    "            return res+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDeletion(self, nums: List[int]) -> int:\r\n",
    "        negans=0\r\n",
    "        a=-1\r\n",
    "        i=0\r\n",
    "        while i < len(nums):\r\n",
    "            if a==-1:\r\n",
    "                a=nums[i]\r\n",
    "            elif nums[i]!=a:\r\n",
    "                negans+=2\r\n",
    "                a=-1\r\n",
    "            i+=1\r\n",
    "        return len(nums)-negans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        p0 = 0\n",
    "        ans = 0\n",
    "        while p0 < len(nums):\n",
    "            n = nums[p0]\n",
    "            p1 = p0 + 1\n",
    "            while p1 < len(nums) and nums[p1] == n:\n",
    "                ans += 1\n",
    "                p1 += 1\n",
    "            p0 = p1 + 1\n",
    "        \n",
    "        return ans + ((len(nums) - ans) & 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        [1,1,2,3,5]\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        dec = 0\n",
    "        last = None\n",
    "        for (k,v) in enumerate(nums):\n",
    "            if k == 0:\n",
    "                last = v\n",
    "                continue\n",
    "            newoffset = k - dec\n",
    "            iseven = newoffset %2 == 0\n",
    "            if iseven:\n",
    "                pass\n",
    "                last = v\n",
    "            else:\n",
    "                if v != last:\n",
    "                    last = v\n",
    "                else:\n",
    "                    dec += 1\n",
    "        restL = len(nums) - dec\n",
    "        if restL %2 == 0:\n",
    "            return dec\n",
    "        return dec + 1\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.minDeletion([3,8,8,3,1,3,6,0,5,5,7,3,2,1,4,5,6,8]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans = nums[:2]\n",
    "        for i in nums[2:]:\n",
    "            if not (i == ans[-1] == ans[-2]):\n",
    "                ans.append(i)\n",
    "        tans = ans[:1]\n",
    "        for i in ans[1:]:\n",
    "            if not (len(tans) % 2 == 1 and i == tans[-1]):\n",
    "                tans.append(i)\n",
    "        if len(tans) % 2 == 1:\n",
    "            del(tans[-1])\n",
    "        return len(nums) - len(tans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res, i = 0, 0\n",
    "\n",
    "        while i < len(nums) - 1:\n",
    "            # 贪心，遇到不符合的就删除\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                res += 1\n",
    "            else:\n",
    "                i += 1\n",
    "            i += 1\n",
    "        \n",
    "        if (len(nums) - res) % 2 != 0:\n",
    "            res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(0, len(nums) - 1):\n",
    "            if (i - ans) % 2 == 0 and nums[i] == nums[i + 1]: ans += 1\n",
    "        return ans + (len(nums) - ans) % 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = ans = 0\n",
    "        while i < n-1:\n",
    "            if nums[i]== nums[i+1]:\n",
    "                i+=1\n",
    "                ans+=1\n",
    "            else:\n",
    "                i+=2 \n",
    "        if (n-ans) % 2 == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for i in range(n-1):\n",
    "            tmp = i - cnt\n",
    "            if tmp % 2 == 0 and nums[i] == nums[i + 1]:\n",
    "                cnt += 1\n",
    "        if (n - cnt) % 2 == 1:\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        i,ans,s,j=0,0,nums,-1\n",
    "        while j<len(s)-2:\n",
    "            i,j=j+1,j+2\n",
    "            while j<=len(s)-1 and s[j]==s[i]:\n",
    "                j,ans=j+1,ans+1\n",
    "        return ans+1-int(j==len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        i, n = 1, len(nums)\n",
    "        while i < n:\n",
    "            while i < n and nums[i-1] == nums[i]:\n",
    "                i += 1\n",
    "                cnt += 1\n",
    "            i += 2\n",
    "        return cnt+1 if (n-cnt)&1 else cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n,r = len(nums),0\n",
    "        for i in range(n):\n",
    "            if (i-r)%2==0 and i+1<n and nums[i] == nums[i+1]:\n",
    "                r+=1\n",
    "        return r + 1 if (n - r)%2 != 0 else r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        first, second = 0, 1\n",
    "        res = 0\n",
    "        length = len(arr)\n",
    "        while second <= length - 1:\n",
    "            while second <= length - 1 and arr[first] == arr[second]:\n",
    "                second += 1\n",
    "                res += 1\n",
    "            first = second + 1\n",
    "            second = first + 1\n",
    "        if (length - res) % 2 != 0:\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n, cnt = len(nums), 0\n",
    "        for i in range(n):\n",
    "            if (i - cnt) % 2 == 0 and i + 1 < n and nums[i] == nums[i + 1]:\n",
    "                cnt += 1\n",
    "        return cnt + 1 if (n - cnt) % 2 != 0 else cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans, check = 0, True\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] == nums[i + 1] and check:\n",
    "                ans += 1\n",
    "            else:\n",
    "                check = not check\n",
    "        if (n - ans) % 2 != 0:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        res, target, state = [], -1, 1\n",
    "        for index in range(len(nums)):\n",
    "            if state and nums[index] != target:\n",
    "                res.append(nums[index])\n",
    "                target, state = nums[index], 0\n",
    "            elif not state and nums[index] != target:\n",
    "                res.append(nums[index])\n",
    "                target, state = -1, 1\n",
    "\n",
    "        return (len(nums) - len(res)) if len(res) % 2 == 0 else (len(nums) - len(res) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n,i = len(nums),0\n",
    "        ans = n\n",
    "        while i < n:\n",
    "            j = i+1\n",
    "            while j<n and nums[j] == nums[i]:\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                ans -= 2\n",
    "            i = j+1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans, check = 0, True\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] == nums[i + 1] and check:\n",
    "                ans += 1\n",
    "            else:\n",
    "                check = not check\n",
    "        if (n - ans) % 2 != 0:\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        wait = [0 for _ in range(n)]\n",
    "        \n",
    "        # wait = [0]*n\n",
    "        # for ii in range(n):\n",
    "        #     idx = ii\n",
    "        #     while idx+1<n:\n",
    "        #         if nums[idx]!=nums[idx+1]:\n",
    "        #             wait[ii]+=2\n",
    "        #         else:\n",
    "        #             break\n",
    "        #         idx+=2\n",
    "        res = 0\n",
    "        idx = 0\n",
    "        flag = 0\n",
    "        while idx<n:\n",
    "            if idx+1>=n:\n",
    "                res+=1\n",
    "                idx+=1\n",
    "            else:\n",
    "                if nums[idx]==nums[idx+1]:\n",
    "                    idx+=1\n",
    "                    res+=1\n",
    "                else:\n",
    "                    idx+=2\n",
    "        return res\n",
    "        \n",
    "            \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = ans = 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 2\n",
    "        return ans + 1 if (n - ans) % 2 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        l=len(nums)\n",
    "        i=l-1\n",
    "        while i>=0:\n",
    "            while i-1>=0 and nums[i]==nums[i-1]:\n",
    "                nums.pop(i-1)\n",
    "                i-=1\n",
    "            if i==0:\n",
    "                nums.pop(0)\n",
    "            i-=2\n",
    "        return l-len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        else:\n",
    "            op=[nums[0]]\n",
    "            for i in range(1,len(nums)):\n",
    "                if (len(op)-1)%2!=0:\n",
    "                    op.append(nums[i])\n",
    "                if (len(op)-1)%2==0:\n",
    "                    if nums[i]!=op[len(op)-1]:\n",
    "                        op.append(nums[i])\n",
    "            if len(op)%2!=0:\n",
    "                return len(nums)-len(op)+1\n",
    "            else:\n",
    "                return len(nums)-len(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        j=1\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            if j==n:\n",
    "                return ans+1\n",
    "            if i==n-1:\n",
    "                return ans+1\n",
    "            # print(i,j,nums[i],nums[j])\n",
    "            if nums[i]==nums[j]:\n",
    "                ans+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                i=j+1\n",
    "                j=i+1\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < n-1:\n",
    "            if nums[i] == nums[i+1]:\n",
    "                # ans.append(nums[i])\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += [nums[i], nums[i+1]]\n",
    "                i += 2\n",
    "        # print(ans, cnt)\n",
    "        if (n-cnt)%2 == 1:\n",
    "            cnt += 1\n",
    "        # print(cnt)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletion(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = ans = 0\n",
    "        while i < n - 1:\n",
    "            if nums[i] == nums[i + 1]:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 2\n",
    "        ans += (n - ans) % 2\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
